-module(chop).
-export([chop/2]).

%% 二分查找程序
%% 输入: Value 要查找的值
%%       Array 有序数组
%% 输出: -1 未查找到该值 或 索引
%% DAY 1
%% chop(_Value, []) ->
%%     -1;
%% chop(Value, Array) ->
%%     chop_help(Value, Array, 1, length(Array)).

%% chop_help(_Value, _Array, First, Last) when First > Last ->
%%     -1;
%% chop_help(Value, Array, First, Last) ->
%%     Mid = (First + Last) div 2,
%%     MidValue = lists:nth(Mid, Array),
%%     if 
%%         Value == MidValue -> Mid;
%%         Value < MidValue -> chop_help(Value, Array, First, Mid-1);
%%         true -> chop_help(Value, Array, Mid+1, Last)
%%     end.

%% DAY 2
%% chop(_Value, []) ->
%%     -1;
%% chop(Value, Array) ->
%%     Mid = (1 + length(Array)) div 2,
%%     MidValue = lists:nth(Mid, Array),
%%     if
%%         Value == MidValue -> Mid;
%%         Value < MidValue -> 
%%             LeftList = lists:sublist(Array, Mid-1),
%%             NowIndex = chop(Value, LeftList),
%%             compute_index(NowIndex, 0);
%%         true -> % Value > MidValue
%%             RightList = lists:sublist(Array, Mid+1, length(Array) - Mid),
%%             NowIndex = chop(Value, RightList),
%%             compute_index(NowIndex, Mid)
%%     end.

%% compute_index(NowIndex, BaseIndex) ->
%%     case NowIndex of
%%         -1 -> -1;
%%         _ -> NowIndex + BaseIndex
%%     end.

%% DAY3
%% 前面两天分别使用数组区间下标和子数组来代表区间，这次使用数组开始下标和
%% 数组长度来表示区间
%% chop(Value, Array) -> 
%%     chop_help(Value, Array, 1, length(Array)).
%%  
%% chop_help(_Value, _Array, _Index, Length) when Length =< 0 ->
%%     -1;
%% chop_help(Value, Array, Index, Length) ->
%%     Mid = Index + Length div 2,
%%     MidValue = lists:nth(Mid, Array),
%%     if 
%%         Value == MidValue -> Mid;
%%         Value < MidValue ->
%%             chop_help(Value, Array, Index, Mid - Index);
%%         true ->
%%             chop_help(Value, Array, Mid + 1, Length - (Mid - Index) - 1)
%%     end.

%% DAY4 2012-05-30
%% 前面的方法都是使用递归的方法，这里使用迭代的方法；
%% 然而erlang无实际的循环语句，因此需像scheme一样使用递归模拟迭代；
%%  |
%% 第一种方法其实已经是迭代的方法了。
%%
%% 循环一个数组和二分查找最本质的区别在于，循环数组只需要下标就行了，而
%% 二分查找需要两个下标。即要查看的元素由一个下标确定或由两个下标确定。
%% 那么是否可以用for语句来二分查找呢?
%% for i,j=0; i<j; ; {
%%   ...
%% }
%%
%% 二分法，区间的缩小方式是平均分，我们也可以按照比率分。这样，
%% 给定区间[begin, end]，区间的缩小方式可以为：
%% (mid-begin) / (end-mid) = p
%% ==> mid = (p*end + begin) / (1+p), 其中 p in (0, 1)
%% p 可以取黄金分割比率，1.618
chop(Value, Array) ->
   chop_help(Value, Array, 1, length(Array)).

chop_help(_Value, _Array, First, Last) when First > Last ->
    -1;
chop_help(Value, Array, First, Last) when First == Last ->
    MidValue = lists:nth(First, Array),
    if 
        Value == MidValue -> First;
        true -> -1
    end;
chop_help(Value, Array, First, Last) ->
    Mid = compute_mid(First, Last, 1.618),
    io:format("~p ~p ~p~n", [First, Last, Mid]),
    MidValue = lists:nth(Mid, Array),
    if 
        Value == MidValue -> Mid;
        Value < MidValue -> chop_help(Value, Array, First, Mid-1);
        true -> chop_help(Value, Array, Mid+1, Last)
    end.

compute_mid(First, Last, Rate) ->
    Mid = (Rate * Last + First) / (1 + Rate),
    erlang:trunc(Mid).
